package lib

//link to 78 90
func init() {
	Probs = append(Probs, Problem{
		Num:         77,
		Discription: "n个整数中k个数的排列组合",
		Level:       2,
		Labels: map[string]int{
			"递归": 1,
			"去重": 1,
		},
	})
}

func Combine(n int, k int) [][]int {
	res := make([][]int, 0)
	comb := make([]int, 0)

	//记录开始查找的位置和已经确定的数字个数，为了不重复
	var travel func(int, int)
	travel = func(count int, start int) {
		if count == k {
			res = append(res, append([]int(nil), comb...))
			return
		}

		//根据已确定的数字个数，缩小遍历范围，不做无意义的查找
		for i := start; i <= n-k+count; i++ {
			comb = append(comb, i+1)
			count++
			travel(count, i+1)
			count--
			comb = comb[:len(comb)-1]
		}
	}

	travel(0, 0)
	return res
}
